原题地址：N皇后 II
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
回溯算法
与 N皇后 是同一个问题，只是最后不需要返回所有解，只需要返回解的数量即可：
/**
* @param {number} n
* @return {number}
*/
const totalNQueens1 = function(n) {
// 记录皇后的位置，下标为行，值为列
let queen = new Array(n).fill(-1);
let result = [];
/**
* 判断新的皇后放在某一行是不是有效的
* @param row 行数
* @returns {boolean} 是否合法
*/
const isOk = (row) => {
// 依次判断已经放置的皇后是否在同一列或同一对角线上
for (let i = 0; i < row; i ++) {
if (queen[i] === queen[row] || // 同一列有两个皇后
row - queen[row] === i - queen[i] || row + queen[row] === i + queen[i]) { // 对角线
return false;
}
}
return true;
};
/**
* 放置某一行的皇后
* @param row 行号
*/
const placeQueen = (row) => {
// n个皇后已经放置完毕，方案可行，将该方案加入结果集
if (row === n) {
result.push([...queen]);
} else {
// 依次尝试放皇后放在每一列，判断该方案是否OK，如果OK就继续放置下一行
// 否则证明该方案不可行，剪枝
for (let column = 0; column < n; column ++) {
queen[row] = column;
if (isOk(row)) {
placeQueen(row + 1);
}
}
}
};
// 从第一行开始放置皇后
placeQueen(0);
// 返回解的数量
return result.length;
};
测试：
let start = new Date();
const test = totalNQueens1;
console.log(test(4)); // 2
console.log(test(5)); // 10
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度： 时间复杂度为$O(n!)$
空间复杂度： 空间复杂度为$O(n)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 7,2019